package problem_everyday;

import java.util.*;

public class D2025_06_28_P2099 {
    /*
    *    n = nums.length
    *       k <= n
    *   使用排序的复杂度 O(n log n)
    *   更改为找第k大的值 + 扫描 O (log n + n) = O(n)
    * */


    // 基于排序
    public int[] maxSubsequence_old(int[] nums, int k) {
        // top-k
        Integer[] nums_tmp = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            nums_tmp[i] = nums[i];
        }
        Arrays.sort(nums_tmp, (a, b) -> b-a);
        int[] res = new int[k];
        int min_num = nums_tmp[k-1];
        int min_num_count = 0;
        int i=k-1;
        while(i>=0&&nums_tmp[i] == min_num){
            min_num_count ++;
            i--;
        }
        i=0;
        for(int j=0; j<nums.length; j++){
            if(nums[j]>min_num){
                res[i++]=nums[j];
            } else if(nums[j]==min_num && min_num_count > 0){
                res[i++]=nums[j];
                min_num_count --;
            }
        }
        return res;
    }

    // 基于快排
    private int quickSelect(int [] nums, int k, int left, int right){
        if(right <= left){
            return nums[left];
        }
        int pivot_index = partition(nums, left, right);
        int bigger_num = right - pivot_index +1;
        if(bigger_num == k) return nums[pivot_index];
        else if(bigger_num < k) return quickSelect(nums, k-bigger_num, left, pivot_index-1);
        else return quickSelect(nums, k, pivot_index+1, right);
    }

    private int partition(int [] nums, int left, int right){
        int pivot_index = right;
        int pivot = nums[right];
        int i=left-1;
        for(int j=left; j<right; j++){
            if(nums[j]<pivot){
                i++;
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
        int temp = nums[i+1];
        nums[i+1] = pivot;
        nums[pivot_index] = temp;
        return i+1;
    }

    public int[] maxSubsequence(int[] nums, int k) {
        // top-k
        int[] nums_tmp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            nums_tmp[i] = nums[i];
        }
        int min_num = quickSelect(nums_tmp, k, 0, nums.length-1);
        int[] res = new int[k];
        int bigger_cnt = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i]>min_num) bigger_cnt ++;
        }
        int i=0, min_num_count = k - bigger_cnt;
        for(int j=0; j<nums.length; j++){
            if(nums[j]>min_num){
                res[i++]=nums[j];
            } else if(nums[j]==min_num && min_num_count > 0){
                res[i++]=nums[j];
                min_num_count --;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        D2025_06_28_P2099 p = new D2025_06_28_P2099();
        int[] nums = {33,-27,-9,-83,48};
        int k=2;
        int[] res = p.maxSubsequence(nums, k);
        for(int a: res){
            System.out.println(a+" ");
        }
    }
}
